package arithmetic.sort;

import java.io.*;
import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * Created by jiangfeng on 2017/10/9.
 */
class TestSort {
    public static void main(String[] args) {
//		Integer[] a = {3, 1, 2, 11, 9, 2, 4, 7, 6, 5, 8,0,10,1,0,1,0,1};
//		Integer[] a = {7, 3, 4,10,8,2,11};
        Integer[] a = {10,8,2,6,3,7,1,13,4};
//		Integer[] a= createRandomArray(10000);
//		printlnArr(a);
        Object o =null;
     //   File file = new File("array.txt");
//		writeArray(a,file);
   //     Integer[] a = readArray(file);
        printlnArr(a);
        Long start=System.currentTimeMillis();

//		ShellSort.shellSort3(a);
//		shellSort(a);
        quickSort(a,0,a.length-1);
//		InsertSort.insertSort(a);
//		BubbleSort.bubbleSort(a);
//		ShellSort.shellSort2(a);
//		MergeSort2.mergeSort(a); // 4 到7
//		MergeSort.mergeSort(a);	// 8 到16
        System.out.println("-----------------------");
        System.out.println(System.currentTimeMillis()-start);
        printlnArr(a);
    }

    /**
     * 测试方法， 创建个数为n 随机数组
     */
    public static Integer[] createRandomArray(int n){
        Integer[] a= new Integer[n];
        Random r =new Random();
        for(int i=0;i<n;i++){
            a[i]=r.nextInt(n);
        }
        return a;
    }

    public static void writeArray(Integer[] array, File file) {
        // file = new File("array.text");
        BufferedOutputStream fos = null;
        try {
            if (!file.exists()) file.createNewFile();
            fos = new BufferedOutputStream(new FileOutputStream(file));
            for (int i = 0; i < array.length; i++) {
                fos.write(array[i]);
            }
        } catch (Exception e) {
        } finally {
            try {
                fos.flush();
                fos.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    public static Integer[] readArray(File file){
//		File file = new File("array.text");
        BufferedInputStream fis =null ;
        List<Integer> list =new ArrayList<Integer>();
        try{
            fis = new BufferedInputStream(new FileInputStream(file));
            int value=0;
            while ((value = fis.read()) != -1) {
                list.add(value);
            }
        }catch (Exception e){
        }finally {
            try {
                fis.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return  list.toArray(new Integer[list.size()]);
    }

    public static void printlnArr(Integer[] a){
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]);
            System.out.print(", ");
        }
        System.out.println();
    }

    public static void shellSort(Integer[] a) {
        for (int gap = a.length / 2; gap > 0; gap /= 2)// 按不同步长分组，每次折半
            for (int i = gap; i < a.length; i++)//排序每个组
                for (int j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)// 每组内的插入排序
                    swap(j, j + gap, a);
    }

    static int count=1;
    public static void quickSort(Integer[] a, int left, int right) {
        System.out.println(MessageFormat.format("left:{0},right:{1} count:{2}",left,right,count++));
        if(left >= right) return;
        int i=left;
        for(int j=left;j<right;j++){
            if(a[j]<a[right]){
                 swap2(i++, j, a);
            }
        }
        swap(i,right,a);//
        quickSort(a,left,i-1);
        quickSort(a,i+1,right);
    }


    public static void  swap(int i, int j, Integer[] a) {
        int temp = 0;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        System.out.print(MessageFormat.format("i:{0}, j:{1}  ",i,j));
        printlnArr(a);
    }

    public static void  swap2(int i, int j, Integer[] a) {
        int temp = 0;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        System.out.print(MessageFormat.format("i:{0}, j:{1} inner ",i,j));
        printlnArr(a);
    }
}
